1. Field of the Invention
The present invention relates to cryptography and methods for encrypting messages for transmission over an insecure communications channel, and particularly to a method for elliptic curve scalar multiplication in a cryptographic system that uses parameterized projective coordinates.
2. Description of the Related Art
Cryptography provides methods of providing privacy and authenticity for remote communications and data storage. Privacy is achieved by encryption of data, usually using the techniques of symmetric cryptography (so called because the same mathematical key is used to encrypt and decrypt the data). Authenticity is achieved by the functions of user identification, data integrity, and message non-repudiation. These are best achieved via asymmetric (or public-key) cryptography.
In particular, public-key cryptography enables encrypted communication between users that have not previously established a shared secret key between them. This is most often done using a combination of symmetric and asymmetric cryptography: public-key techniques are used to establish user identity and a common symmetric key, and a symmetric encryption algorithm is used for the encryption and decryption of the actual messages. The former operation is called key agreement. Prior establishment is necessary in symmetric cryptography, which uses algorithms for which the same key is used to encrypt and decrypt a message.
Public-key cryptography, in contrast, is based on key pairs. A key pair consists of a private key and a public key. As the names imply, the private key is kept private by its owner, while the public key is made public (and typically associated to its owner in an authenticated manner). In asymmetric encryption, the encryption step is performed using the public key, and decryption using the private key. Thus, the encrypted message can be sent along an insecure channel with the assurance that only the intended recipient can decrypt it.
The key agreement can be interactive (e.g., for encrypting a telephone conversation) or non-interactive (e.g., for electronic mail).
User identification is most easily achieved using what are called identification protocols. A related technique, that of digital signatures, provides data integrity and message non-repudiation in addition to user identification. The public key is used for encryption or signature verification of a given message, and the private key is used for decryption or signature generation of the given message.
The use of cryptographic key pairs was disclosed in U.S. Pat. No. 4,200,770, issued Apr. 29, 1980 to Hellman et al., entitled “CRYPTOGRAPHIC APPARATUS AND METHOD.” The '770 patent also disclosed the application of key pairs to the problem of key agreement over an insecure communication channel. The algorithms specified in the '770 patent rely for their security on the difficulty of the mathematical problem of finding a discrete logarithm. U.S. Pat. No. 4,200,770 is hereby incorporated by reference in its entirety.
In order to undermine the security of a discrete logarithm-based cryptographic algorithm, an adversary must be able to perform the inverse of modular exponentiation (i.e., a discrete logarithm). There are mathematical methods for finding a discrete logarithm (e.g., the Number Field Sieve), but these algorithms cannot be done in any reasonable time using sophisticated computers if certain conditions are met in the specification of the cryptographic algorithm.
In particular, it is necessary that the numbers involved be large enough. The larger the numbers used, the more time and computing power is required to find the discrete logarithm and break the cryptograph. On the other hand, very large numbers lead to very long public keys and transmissions of cryptographic data. The use of very large numbers also requires large amounts of time and computational power in order to perform the cryptographic algorithm. Thus, cryptographers are always looking for ways to minimize the size of the numbers involved, and the time and power required, in performing the encryption and/or authentication algorithms. The payoff for finding such a method is that cryptography can be done faster, cheaper, and in devices that do not have large amounts of computational power (e.g., handheld smart cards).
A discrete-logarithm based cryptographic algorithm can be performed in any mathematical setting in which certain algebraic rules hold true. In mathematical language, the setting must be a finite cyclic group. The choice of the group is critical in a cryptographic system. The discrete logarithm problem may be more difficult in one group than in another for which the numbers are of comparable size. The more difficult the discrete logarithm problem, the smaller the numbers that are required to implement the cryptographic algorithm. Working with smaller numbers is easier and faster than working with larger numbers. Using small numbers allows the cryptographic system to be higher performing (i.e., faster) and requires less storage. So, by choosing the right kind of group, a user may be able to work with smaller numbers, make a faster cryptographic system, and get the same, or better, cryptographic strength than from another cryptographic system that uses larger numbers.
The groups referred to above come from a setting called finite fields. Methods of adapting discrete logarithm-based algorithms to the setting of elliptic curves are known. However, finding discrete logarithms in this kind of group is particularly difficult. Thus, elliptic curve-based cryptographic algorithms can be implemented using much smaller numbers than in a finite field setting of comparable cryptographic strength. Thus, the use of elliptic curve cryptography is an improvement over finite field-based public-key cryptography.
In practice, an Elliptic Curve group over Fields F(p), denoted as E(p), is formed by choosing a pair of a and b coefficients, which are elements within F(p). The group consists of a finite set of points P(x,y) that satisfy the elliptic curve equation:F(x,y)=y2−x3−ax−b=0  (1.1)together with a point at infinity, O. The coordinates of the point, x and y, are elements of F(p) represented in N-bit strings. In what follows, a point is either written as a capital letter, e.g., P, or as a pair in terms of the affine coordinates, i.e., (x,y).
The Elliptic Curve Cryptosystem relies upon the difficulty of the Elliptic Curve Discrete Logarithm Problem (ECDLP) to provide its effectiveness as a cryptosystem. Using multiplicative notation, the problem can be described as: given points B and Q in the group, find a number k such that Bk=Q, where k is called the discrete logarithm of Q to the base B. Using additive notation, the problem becomes: given two points B and Q in the group, find a number k such that kB=Q.
In an Elliptic Curve Cryptosystem, the large integer k is kept private and is often referred to as the secret key. The point Q together with the base point B are made public and are referred to as the public key. The security of the system, thus, relies upon the difficulty of deriving the secret k, knowing the public points B and Q. The main factor that determines the security strength of such a system is the size of its underlying finite field. In a real cryptographic application, the underlying field is made so large that it is computationally infeasible to determine k in a straightforward way by computing all the multiples of B until Q is found.
The core of elliptic curve geometric arithmetic is an operation called scalar multiplication, which computes kB by adding together k copies of the point B. Scalar multiplication is performed through a combination of point doubling and point addition operations. The point addition operation adds two distinct points together and the point doubling operation adds two copies of a point together. To compute, for example, 11B=(2*(2*(2B)))+3B=Q, it would take three point doublings and one point-addition.
Addition of two points on an elliptic curve is calculated as follows. When a straight line is drawn through the two points, the straight line intersects the elliptic curve at a third point. The point symmetric to this third intersecting point with respect to the x-axis is defined as a point resulting from the addition.
Doubling a point on an elliptic curve is calculated as follows. When a tangent line is drawn at a point on an elliptic curve, the tangent line intersects the elliptic curve at another point. The point symmetric to this intersecting point with respect to the x-axis is defined as a point resulting from the doubling.
Table 1 illustrates the addition rules for adding two points (x1,y1) and (x2,y2), that is,(x3,y3)=(x1,y1)+(x2,y2)  (1.2)
TABLE 1Summary of Addition RulesGeneral Equationsx3 = m3 − x2 − x1y3 = m(x3 − x1) + y1 Point Addition  m  =                    y        2            -              y        1                            x        2            -              x        1             Point Doubling (x3, y3) = 2(x1, y1)  m  =                    3        ⁢                                  ⁢                  x          1          2                    -      a              2      ⁢                          ⁢              y        1             (x2, y2) = −(x, y1)(x3, y3) = (x1, y1) + (−(x1, y1)) = O(x2, y2) = O(x3, y3) = (x1, y1) + O =−(x1, y1)(x1, y1) = (x1, −y1)
Given a message point (xm, ym), a base point (xB, yB), and a given key, k, the cipher point (xC, yC) is obtained using the following equation,(xc,yc)=(xm,ym)+k(xB,yB)  (1.3)There are two basics steps in the computation of the above equations. The first is to find the scalar multiplication of the base point with the key, “k(xB,yB)”. The resulting point is then added to the message point, (xm, ym) to obtain the cipher point. At the receiver, the message point is recovered from: the cipher point, which is usually transmitted; the shared key; and the base point, that is(xm,ym)=(xc,yc)−k(xB,yB)  (1.4)
The steps of elliptic curve symmetric cryptography can be summarized as follows. Both the sender and receiver must agree on: (1) A random number, k, that will be the shared secret key for communication; and (2) A base point, P=(XB, YB).
At the sending correspondent, (1) Embed a message bit string into the x coordinate of an elliptic curve point, which is designated as the message point, (xm, ym); (2) The cipher point (xc, Yc) is computed using, (xc,yC)=(xm,ym)+k(xB,yB); and (3) The appropriate bits of the x-coordinate and the sign bit of the y-coordinate of the cipher point (xc, yc) are sent to the receiving entity.
At the receiving correspondent, the following steps are performed. (1) Using the shared key, k, and the base point (xB, yB), the scalar multiplication (xBk, yBk)=k(xB, yB) is computed; (2) The message point (xm,ym) is computed using (xm,ym)=(xc,yc)+(−k(xB,yB)); and (3) The secret message's bit string is recovered from xm.
The steps of elliptic curve public-key cryptography can be summarized as follows. Both the sender and receiver must agree on (1) An elliptic curve; and (2) A base point, P=(xB, yB). At the sending correspondent, (1) Embed a message bit string into the x-coordinate of an elliptic curve point, which is designated as the message point, (xm, ym); (2) Using the private key of the sending correspondent, kSPr, and the public key of the receiving correspondent, kRPr(xb, yb), compute the scalar multiplication (xbk, ybk)=kSPr(kRPr(xb,yb)); (3) Compute a cipher point (xc,yc) using (xc,yc)=(xm,ym)+(xbk, ybk); and (4) Send appropriate bits of the x-coordinate and the sign bit of the y-coordinate of the cipher point (xc,yc) to the receiving correspondent.
At the receiving correspondent, (1) Using the private key of the receiving correspondent, kRPr, and the public key of the sending correspondent, kSPr(xb, yb), compute the scalar multiplication (xbk, ybk)=kRPr(kSPr(xb, yb)); (2) Compute the message point (xm,ym) using (xm,ym)=(xc,yc)−(xbk, ybk); and (3) Recover the message bit string from Xm.
Scalar multiplication (SM) (or point multiplication) refers to computing the point:KP=P+P+P+ . . . P(sum taken K times)on the elliptic curve over a given finite field. The integer K is referred to as “scalar” and the point P as the base point. Adding the point P to itself K times is not an efficient way to compute scalar multiplication. More efficient methods are based on a sequence of addition (ADD) and doubling (DBL) operations. The doubling operation is simply adding the point to itself.
The computation of the point KP processed by the scalar multiplication is performed using the binary expression of K represented by the equation:K=kn−12n-1+kn−22n-2+ . . . +k12+k0,  (1.5)where ki is the i-th bit of the binary representation of K, and n is the total number of bits.
There are two main methods of calculating KP. The Least-to-Most (LM) algorithm, which starts from the least significant bit of K, and the Most-to-Least (ML) algorithm which starts from the most significant bit of K. The LM and the ML algorithms are shown below.
Algorithm 1: Least-to-Most Binary Method AlgorithmINPUT    K, POUTPUT   KP   1. Initialize Q[0] = O, Q[1] = P   2. for i=0 to n−1   3.   if k[i]==1 then   4.     Q[0]=ADD(Q[0],Q[1])   5.   end if   6.   Q[1]=DBL(Q[1])   7. end for   8. return Q[0]
In the LM algorithm, Q[0] is initialized to the identity point O, and Q[1] is initialized to the base point P. If ki=1, the elliptic curve addition, ADD, is performed on the points Q[0] and Q[1] in step 4, and the result is stored in the point Q[0]; otherwise, (i.e., for ki=0) Q[0] remains unchanged. The elliptic curve doubling, DBL, is performed on the point Q[1] in step 6, and the result is stored in the point Q[I]. This point doubling operation in step 6 is performed in all cases, regardless of the scalar bit value.
Algorithm 2: Most-to-Least Binary Method AlgorithmINPUT    K, POUTPUT   KP   1. Initialize Q[0] = P   2. for i= n−2 downto 0   3.   Q[0]=DBL(Q[0])   4.   if k[i]==1 then   5.     Q[0]=ADD(Q[0],P)   6.   end if   7. end for   8. return Q[0]
The ML algorithm treats the bit string of K starting with the most significant bit first. Since the most significant bit is always 1, the ML algorithm starts from the nextmost bit, n−2, and initializes Q[0] to P. This kind of algorithm needs only one variable, Q[0]. First, the DBL operation is performed on Q[0], and the result is stored in Q[0], as shown in step 3. This point doubling in step 3 is performed regardless of the scalar bit value. If ki=1, the ADD operation is performed on the point Q[0] and the base point P in step 5, and the result is stored in point Q[0]; otherwise, (i.e. for ki=0) Q[0] remains unchanged.
The difficulty in solving the elliptic curve discrete logarithm problem has been established theoretically. However, information associated with secret information, such as the private key or the like, may leak out in cryptographic processing in real mounting. Thus, there has been proposed an attack method of so-called power analysis, in which the secret information is decrypted on the basis of the leaked information.
An attack method in which change in voltage is measured in cryptographic processing using secret information, such as DES (Data Encryption Standard) or the like, so that the process of the cryptographic processing is obtained and the secret information inferred on the basis of the obtained process, is called DPA (Differential Power Analysis).
As shown in Algorithm 1 and Algorithm 2, performing the ADD operation is conditioned by the key bit. If the scalar bit value is equal to one, an ADD operation is performed; otherwise, an ADD operation is not performed. Therefore, a simple power analysis (i.e., simple side channel analysis using power consumption as the side channel) will produce different power traces that distinguish between the existence of an ADD operation or not. This can reveal the bit values of the scalar.
One widely used approach to avoid this kind of leak to perform a dummy addition in the ML method when the processed bit is ‘0’ so that each iteration appears as a doubling followed by an addition operation, which is called the “Double-and-ADD always algorithm”, shown below for the ML technique as Algorithm 3, with a similar algorithm for the LM technique shown below as Algorithm 4.
Algorithm 3: ML Double-and-ADD always algorithmINPUT  K,POUTPUT KP  1. Initialize Q[2]=P  2. for i=n−2 downto 0  3.   Q[0]=DBL(Q[2])  4.   Q[1]=ADD(Q[0],P)  5.   Q[2]=Q[ki]  6. end for   return Q[2]
Algorithm 4: LM Double-and-ADD always algorithmINPUT  K,POUTPUT KP  1. Initialize Q[2]=P  2. for i=n−2 downto 0  3.   Q[0]=DBL(Q[2])  4.   Q[1]=ADD(Q[0],P)  5.   Q[2]=Q[ki]  6. end for   return Q[2]
Another ML algorithm to avoid this kind of leak is disclosed in U.S. Patent Application No. 2003/0123656, published Jul. 3, 2003, entitled “ELLIPTIC CURVE CRYPTOSYSTEM APPARATUS, STORAGE MEDIUM STORING ELLIPTIC CURVE CRYPTOSYSTEM PROGRAM, AND ELLIPTIC CURVE CRYPTOSYSTEM ARITHMETIC METHOD”. This algorithm uses extra ADD operations to assure that the sequence of DBL and ADD operations is carried out in each iteration. We refer to this algorithm as Takagi's algorithm, shown below as Algorithm 5.
Algorithm 5: Takagi's ML algorithmINPUT     K,POUTPUT    KP  1. INITIALIZE Q[0]=P; Q[1]=2P  2. for i=n−2 down to 0  3.   Q[2]=DBL(Q[ki])  4.   Q[1]=ADD(Q[0],Q[1])  5.   Q[0]=Q[2−ki]  6.   Q[1]=Q[1 + ki]  7. end for   return Q[0]
Even if an algorithm is protected against single power analysis, it may succumb to the more sophisticated differential power analysis (DPA). Assume that the double-and-add always method is implemented with one of the previous algorithms given in Algorithms 3, 4 or 5. Representing the scalar value K in binary:K=kn−12n-1+kn−22n-2+ . . . +ki2+k0,  (1.6)where ki is the i-th bit of the binary representation of K, and n is the total number of bits. DPA is based on the assumption that an attacker already knows the highest bits, kn−1, kn−2, . . . kj+1 of K. Then, he guesses that the next bit kj is equal to ‘1’, and then randomly chooses several points P1, . . . , Pt and computes:
                              Q          r                =                                            (                                                ∑                                      i                    =                    j                                                        n                    -                    1                                                  ⁢                                                      k                    i                                    ⁢                                      2                                          i                      -                      j                                                                                  )                        ⁢                          P              r                        ⁢                                                  ⁢            For            ⁢                                                  ⁢            1                    ≤          r          ≤                      t            .                                              (        2.1        )            
Based on statistical analysis of these points (i.e., Qr, 1≦r≦t), he can decide whether his guess is correct or not. Once kj is known, the remaining bits, kj−1, kj−2, . . . , k0, are recovered recursively in the same way.
J. Coron proposed the following randomization-based countermeasures, which are effective against differential power analysis attacks: (1) Randomizing the base-point P by computing Q=kP as Q=(P+R)−kR for a random point R; (2) Using randomized projective coordinates, i.e., for a random number r≠0, the projective coordinates, (X, Y, Z) and (rX; rY, rZ) represent the same point, so that for a random number r, if P=(x0,y0), Q is computed as Q=k(rx0, ry0: r); (3) Randomizing the scalar K, i.e., if n=ordE(P) denotes the order of PεE(F(p)), then Q is computed as Q=(k+rn)P for a random r, or, alternatively, one can replace n by the order of the elliptic curve, #E(F(p)).
These countermeasures can be used with Coron's algorithm or Takagi's algorithm to protect scalar multiplication computation against both simple power attacks and differential power analysis attacks.
One of the crucial decisions when implementing an efficient elliptic curve cryptosystem over GF(p) is deciding which point coordinate system to use. The point coordinate system used for addition and doubling of points on the elliptic curve determines the efficiency of these routines, and hence the efficiency of the basic cryptographic operation, scalar multiplication
There are many techniques proposed for fast implementations of elliptic curve cryptosystems. One of the most important techniques that can be used to enhance scalar multiplication is the idea of transferring the point coordinates into other coordinates that can eliminate the inverse operation.
Various coordinates can be used in order to eliminate the inverse operation in scalar multiplication and, hence, increase the speed of calculations. We still need one final inverse operation to return back to the normal (Affine) coordinates after completing scalar multiplication. There are potentially five different coordinate systems, which can be summarized as: Affine (A), Projective (P), Jacobian (J), Chudnovsky-jacobian (C), and Modified (M) coordinates. The computation times in terms of number of multiplication (M), squaring (S), and inverse (I) operations are computed for each coordinate system. For simplicity, the addition and subtraction operations are not considered, since they require very little time.